//
// Created by 高森森 on 2022/1/30.
//

#ifndef LEETCODE_SOLUTION16_H
#define LEETCODE_SOLUTION16_H
#include <iostream>
#include <vector>
#include <queue>
#include<unordered_map>
using namespace std;

class Solution16 {
private:
    static const int mod=1000000007;
public:
    int dfs(int n,int u,vector<vector<int>>&graph,  vector<int>&f){
        if(u==n-1)
            return 1;
        if(f[u]!=-1)
            return f[u];
        f[u]=0;
        for(int i:graph[u]){
            f[u]+=dfs(n,i,graph,f);
            if(f[u]>=mod)
                f[u]-=mod;
        }
        return f[u];
    }
    int countPaths(int n, vector<vector<int>>& roads) {
        vector<vector<long long>>dist(n,vector<long long>(n,LLONG_MAX/2));
        for(int i=0;i<n;i++)
            dist[i][i]=0;
        for(auto &road:roads) {
            dist[road[0]][road[1]]=road[2];
            dist[road[1]][road[0]]=road[2];
        }
        //可以采用Floyd或者Dijksta求单源最短路径
        vector<int>visieted(n);
        for(int i=0;i<n;i++){
            int u=-1;
            for(int j=0;j<n;j++){
                if(!visieted[j]&&(u==-1||dist[0][j]<dist[0][u])){
                    u=j;
                }
            }
            visieted[u]=true;
            for(int k=0;k<n;k++) {
                dist[0][k] = min(dist[0][k], dist[0][u] + dist[u][k]);
            }
        }
        vector<vector<int>>graph(n);
        for(auto &road:roads){
            int x=road[0];
            int y=road[1];
            int z=road[2];
            if(dist[0][x]-dist[0][y]==z){
                graph[y].push_back(x);
            }
            else if(dist[0][y]-dist[0][x]==z){
                graph[x].push_back(y);
            }
        }
        vector<int>f(n,-1);
        return dfs(n,0,graph,f);
    }
};


#endif //LEETCODE_SOLUTION16_H
